package com.gqb.collection;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 中缀转前缀 将中缀表达式转换为前缀表达式： 遵循以下步骤： (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2； (2) 从右至左扫描中缀表达式；
 * (3) 遇到操作数时，将其压入S2； (4) 遇到运算符时，比较其与S1栈顶运算符的优先级： (4-1)
 * 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； (4-3)
 * 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较； (5) 遇到括号时： (5-1)
 * 如果是右括号“)”，则直接压入S1； (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
 * (6) 重复步骤(2)至(5)，直到表达式的最左边； (7) 将S1中剩余的运算符依次弹出并压入S2； (8)
 * 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。 例如，将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程如下：
 * 扫描到的元素 S2(栈底->栈顶) S1 (栈底->栈顶) 说明 5 5 空 数字，直接入栈 - 5 - S1为空，运算符直接入栈 ) 5 - )
 * 右括号直接入栈 4 5 4 - ) 数字直接入栈 × 5 4 - ) × S1栈顶是右括号，直接入栈 ) 5 4 - ) × ) 右括号直接入栈 3 5
 * 4 3 - ) × ) 数字 + 5 4 3 - ) × ) + S1栈顶是右括号，直接入栈 2 5 4 3 2 - ) × ) + 数字 ( 5 4 3
 * 2 + - ) × 左括号，弹出运算符直至遇到右括号 ( 5 4 3 2 + × - 同上 + 5 4 3 2 + × - + 优先级与-相同，入栈 1
 * 5 4 3 2 + × 1 - + 数字 到达最左端 5 4 3 2 + × 1 + - 空 S1中剩余的运算符因此结果为“- + 1 × + 2 3 4
 * 5”。
 * 
 * @author 小泽玛丽罗
 *
 *         这里默认，表达式是合法的，所以中缀转前缀的表达式必须正确
 */
public class Infix2Prefix {
	public static char Left_parenthesis = '(';
	public static char Right_parenthesis = ')';
	public static char[] operatorsA = { '+', '-', '*', '/', '×' };
	public static Map<Character, Integer> priority = new HashMap<Character, Integer>();

	static {
		priority.put('+', 1);
		priority.put('-', 1);
		priority.put('*', 2);
		priority.put('/', 2);
		priority.put('×', 2);
	}

	/**
	 * 中缀转前缀,从右向左扫描
	 * 
	 * @param expression
	 * @return
	 */
	public static String infixTrun2Prefix(String expression) {

		Stack<Character> operators = new Stack<Character>();
		Stack<Character> nums = new Stack<Character>();
		char[] chars = expression.toCharArray();
		for (int i = chars.length - 1; i >= 0; i--) {
			if (chars[i] == Infix2Prefix.Right_parenthesis) {
				operators.push(chars[i]);
			} else if (chars[i] == Infix2Prefix.Left_parenthesis) {
				char op = operators.pop();
				while (op == Infix2Prefix.Right_parenthesis) {
					op = operators.pop();
				}
				nums.push(op);
			} else {
				if (isOperator(chars[i])) {
					operators.push(chars[i]);
				} else {
					nums.push(chars[i]);
				}
			}
		}
		while (!operators.empty()) {
			char x = operators.peek();
			if (x != Infix2Prefix.Right_parenthesis) {
				nums.push(operators.pop());
			} else {
				operators.pop();
			}

		}
		System.out.println(nums.toArray());
		return stack2String(nums);
	}

	/**
	 * 将中缀表达式转换成后缀表达式 中转后，是从左向右扫描，和中转前刚好相反
	 * 
	 * @param expression
	 * @return
	 */
	public static String infix2Suffix(String expression) {
		Stack<Character> operators = new Stack<Character>();
		Stack<Character> nums = new Stack<Character>();
		char[] chars = expression.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] == Infix2Prefix.Left_parenthesis) {
				operators.push(chars[i]);
			} else if (chars[i] == Infix2Prefix.Right_parenthesis) {
				char op = operators.pop();
				while (op != Infix2Prefix.Left_parenthesis) {
					nums.push(op);
					op = operators.pop();
				}
			} else {
				// TODO important,这里如果是运算符，先判断当前运算符的优先级是否高于栈顶的运算符
				// 如果栈顶元素是左括号就压入，不是就要比较优先级，如果优先级<栈顶运算符，则将栈顶运算符压倒 数字的栈中，然后再压入
				if (isOperator(chars[i])) {
					boolean isPushed = false;
					if (operators.isEmpty()) {
						isPushed = true;
						operators.push(chars[i]);
					}
					while (!isPushed) {
						if (operators.isEmpty()) {
							operators.push(chars[i]);
							isPushed = true;
						} else if (operators.peek() == Infix2Prefix.Left_parenthesis) {
							operators.push(chars[i]);
							isPushed = true;
						} else {
							if (priority.get(chars[i]) > priority.get(operators
									.peek())) {
								operators.push(chars[i]);
								isPushed = true;
							} else {
								nums.push(operators.pop());
							}
						}
					}
				} else {
					nums.push(chars[i]);
				}
			}
		}
		while (!operators.empty()) {
			char x = operators.peek();
			if (x != Infix2Prefix.Left_parenthesis) {
				nums.push(operators.pop());
			} else {
				operators.pop();
			}
		}
		return stack2String(nums);
	}

	
	/**
	 * 判断是不是运算符,+,-,*,/
	 * 
	 * @param operator
	 * @return
	 */
	public static boolean isOperator(char operator) {
		for (char c : operatorsA) {
			if (operator == c)
				return true;
		}

		return false;
	}

	public static <E> String stack2String(Stack<E> stack) {
		StringBuilder s = new StringBuilder();
		for (E e : stack) {
			s.append(e);
		}
		return s.toString();
	}

	/**
	 * 判断表达式是否合法，主要判断括号是否对齐
	 * 
	 * @param expression
	 * @return
	 */
	public static boolean isExpressionValid(String expression) {

		return true;
	}

	/**
	 * 用于比较是否 op1运算符的优先级是否大于 op2运算符
	 * 
	 * @param op1
	 * @param op2
	 * @return
	 */
	public static boolean isPriority(char op1, char op2) {
		return true;
	}
}
